πŸ‘©β€πŸ’» 72416. 맀좜 ν•˜λ½ μ΅œμ†Œν™”

@Seongukbaek Posted July 10, 2022 Β· Updated July 10, 2022 Β· 3 min read

문제

Programmers - 맀좜 ν•˜λ½ μ΅œμ†Œν™”

πŸ“ Logic

private static void traversal(int node) { // ν•΄λ‹Ή 직원이 μ›Œν¬μˆμ— μ°Έμ—¬ν•˜μ§€ μ•ŠλŠ” 경우 costs[node][0] = 0; // ν•΄λ‹Ή 직원이 μ›Œν¬μˆμ— μ°Έμ—¬ν•œ 경우 -> ν•΄λ‹Ή 직원 λ§€μΆœμ„ μ €μž₯ costs[node][1] = sales[node]; // 리프 λ…Έλ“œλΌλ©΄, μƒμœ„λ‘œ μ΅œμ†Œ λΉ„μš©μ„ 전달해야 함 if (adjList.get(node).isEmpty()) return; int extraCost = 10001; for (int child : adjList.get(node)) { traversal(child); // μ΅œμ†Œ λΉ„μš©μ„ λΆ€λͺ¨ λ…Έλ“œ(νŒ€μž₯)에 λˆ„μ  if (costs[child][0] < costs[child][1]) { costs[node][0] += costs[child][0]; costs[node][1] += costs[child][0]; // νŒ€μž₯κ³Ό νŒ€μ› λͺ¨λ‘ μ°Έμ—¬ν•˜μ§€ μ•ŠμœΌλ©΄ μ•ˆλ˜κΈ°μ— ν•„μš”ν•œ μΆ”κ°€ λΉ„μš© 계산 extraCost = Math.min(extraCost, costs[child][1] - costs[child][0]); } else { costs[node][0] += costs[child][1]; costs[node][1] += costs[child][1]; // λ‘˜ 쀑 ν•œ λͺ…이라도 μ°Έμ—¬ν–ˆλ‹€λ©΄ μΆ”κ°€ λΉ„μš©μ€ ν•„μš” μ—†μŒ extraCost = 0; } } costs[node][0] += extraCost; }
  • ν•΄λ‹Ή 직원이 μ›Œν¬μˆμ— μ°Έμ—¬ν•œ κ²½μš°μ™€ ν•˜μ§€ μ•Šμ€ κ²½μš°μ— λŒ€ν•œ λΉ„μš©μ„ κ³„μ‚°ν•œλ‹€.
  • λΆ€λͺ¨ λ…Έλ“œμ—μ„œλŠ” μžμ‹ λ…Έλ“œμ˜ λΉ„μš© 정보λ₯Ό μ΄μš©ν•΄ κ²½μš°μ— λ”°λ₯Έ λΉ„μš©μ„ κ³„μ‚°ν•œλ‹€.

    • μ΄λ•Œ, νŒ€μž₯κ³Ό νŒ€μ› λͺ¨λ‘ μ°Έμ—¬ν•˜μ§€ μ•ŠλŠ” κ²½μš°μ— λŒ€ν•œ μΆ”κ°€ λΉ„μš©μ„ κ³„μ‚°ν•œλ‹€.

πŸ“„ CODE

μ½”λ“œ 보기/μ ‘κΈ°πŸ’«
import java.util.*; class Solution { // 직원별 μ›Œν¬μˆμ— μ°Έμ—¬ν–ˆμ„ λ•Œμ˜ 맀좜과 μ°Έμ—¬ν•˜μ§€ μ•Šμ•˜μ„ λ•Œμ˜ 맀좜, 0: μ°Έμ—¬ X, 1: μ°Έμ—¬ O static int[][] costs; static ArrayList<ArrayList<Integer>> adjList = new ArrayList<>(); static int[] sales; public int solution(int[] sales, int[][] links) { this.sales = sales; init(); makeAdjList(links); traversal(0); return Math.min(costs[0][0], costs[0][1]); } private static void init() { costs = new int[sales.length][2]; for (int i = 0; i < sales.length; i++) adjList.add(new ArrayList<>()); } private static void makeAdjList(int[][] links) { for (int[] link : links) adjList.get(link[0] - 1).add(link[1] - 1); } private static void traversal(int node) { // ν•΄λ‹Ή 직원이 μ›Œν¬μˆμ— μ°Έμ—¬ν•˜μ§€ μ•ŠλŠ” 경우 costs[node][0] = 0; // ν•΄λ‹Ή 직원이 μ›Œν¬μˆμ— μ°Έμ—¬ν•œ 경우 -> ν•΄λ‹Ή 직원 λ§€μΆœμ„ μ €μž₯ costs[node][1] = sales[node]; // 리프 λ…Έλ“œλΌλ©΄, μƒμœ„λ‘œ μ΅œμ†Œ λΉ„μš©μ„ 전달해야 함 if (adjList.get(node).isEmpty()) return; int extraCost = 10001; for (int child : adjList.get(node)) { traversal(child); // μ΅œμ†Œ λΉ„μš©μ„ λΆ€λͺ¨ λ…Έλ“œ(νŒ€μž₯)에 λˆ„μ  if (costs[child][0] < costs[child][1]) { costs[node][0] += costs[child][0]; costs[node][1] += costs[child][0]; // νŒ€μž₯κ³Ό νŒ€μ› λͺ¨λ‘ μ°Έμ—¬ν•˜μ§€ μ•ŠμœΌλ©΄ μ•ˆλ˜κΈ°μ— ν•„μš”ν•œ μΆ”κ°€ λΉ„μš© 계산 extraCost = Math.min(extraCost, costs[child][1] - costs[child][0]); } else { costs[node][0] += costs[child][1]; costs[node][1] += costs[child][1]; // λ‘˜ 쀑 ν•œ λͺ…이라도 μ°Έμ—¬ν–ˆλ‹€λ©΄ μΆ”κ°€ λΉ„μš©μ€ ν•„μš” μ—†μŒ extraCost = 0; } } costs[node][0] += extraCost; } }

✏️ Review

  • 접근법을 λͺ°λΌ ν—€λ§€λ‹€κ°€, 풀이 μ˜μƒμ„ μ°Έκ³ ν–ˆλ‹€. 풀이 μ˜μƒμ„ λ³΄λ‹ˆ 이전에도 λΉ„μŠ·ν•œ 문제λ₯Ό ν’€μ—ˆλ˜ 것 κ°™λ‹€. (μžμ‹ λ…Έλ“œμ˜ 정보λ₯Ό μƒμœ„λ‘œ λ„˜κ²¨μ£Όλ©΄μ„œ μ΅œμ†Œ λΉ„μš©μ„ κ΅¬ν•˜λŠ” ...?)
@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€